package java_0220.leetcode;

import java.util.Scanner;

/**
 * 按给出的前序遍历字符串构建二叉树，并将二叉树按中序遍历输出
 */
public class NumCoder_BuildTree {
    public static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(char val) { this.val = val; }
        TreeNode(char val,TreeNode left,TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //表示前序遍历处理到哪个字符了
    private static int index=0;
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        //多组输入
        while(scanner.hasNext()){
            //每次读取一行前序遍历的结果
            String str=scanner.next();
            //根据前序遍历的字符串构建了一棵二叉树
            TreeNode root=preOrderBuilder(str);
            //对其使用中序遍历输出指定值
            inOrder(root);
            //每行输出占一行
            System.out.println();
        }
    }

    private static void inOrder(TreeNode root) {
        if(root==null){
            return;
        }
        //先递归左子树
        inOrder(root.left);
        //根
        System.out.print(root.val+" ");
        //右子树
        inOrder(root.right);
    }

    /**
     * 根据题目所给的前序遍历的字符串构建一个二叉树
     * @param str
     * @return
     */
    private static TreeNode preOrderBuilder(String str) {
        char cur=str.charAt(index);
        if(cur=='#'){
            //空节点，不构建节点
            return null;
        }
        TreeNode root=new TreeNode(cur);
        index++;//表示继续去处理下一个节点
        //递归处理左子树
        root.left=preOrderBuilder(str);
        index++;
        //再递归处理右子树
        root.right=preOrderBuilder(str);
        return root;
    }
}
